package com.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 无重复字符串的最长子串
 *
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * @author winson
 * @create 2022-03-25 15:43
 */
public class LongestSubstringSolution {
    public int lengthOfLongestSubstring(String s) {
        /**
         * 遍历字符数组，假如没有重复字符，长度计算加1，如果有重复，计算开始位置调整，从第一次出现重复字符的下一个位置开始计算
         * 如何判断重复，以及需要记录重复的位置，通过HashMap
         */
        if (s == null) {
            return 0;
        }
        int ans = 0;
        int length = s.length();
        Map<Character, Integer> map = new HashMap<>();
        int start = 0;
        int k = start;
        while (start < length) {
            while (k < length && !map.containsKey(s.charAt(k))) {
                map.put(s.charAt(k), k);
                k++;
            }
            if (k == length) {
                // 遍历到最后一个字符还没有重复
                ans = Math.max(ans, k - start);
                return ans;
            } else {
                ans = Math.max(ans, k - start);
                // 出现重复字符，找到重复字符所在位置，重新计算开始位置
                int p = map.get(s.charAt(k));
                for (int i = 0; i <= p; i++) {
                    // 移除元素前，判断是否在前面
                    if (map.containsKey(s.charAt(i)) && map.get(s.charAt(i)) <= p) {
                        map.remove(s.charAt(i));
                    }
                }
                map.put(s.charAt(k), k);
                start = p + 1;
                k++;
            }
        }
        return ans;
    }

    public int lengthOfLongestSubstring2(String s) {
        /**
         * 滑动计算
         */
        if (s == null || s.length() == 0) {
            return 0;
        }
        int ans = 0;
        int length = s.length();
        int rk = 0;
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < length; i++) {
            if (i != 0) {
                set.remove(s.charAt(i - 1));
            }
            while (rk < length && !set.contains(s.charAt(rk))) {
                set.add(s.charAt(rk));
                rk++;
            }
            ans = Math.max(ans, rk - i);
        }
        return ans;
    }

    public static void main(String[] args) {
        /**
         * 输入: s = "abcabcbb"
         * 输出: 3
         */
        LongestSubstringSolution solution = new LongestSubstringSolution();
        int ans = solution.lengthOfLongestSubstring2("abcabcbb");
        System.out.println(ans);
    }
}
